home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / setc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  11.9 KB  |  475 lines  |  [TEXT/R*ch]
  1. /*
  2.     setc.c -- massive bit-hacking for performing special "cube"-type
  3.     operations on a set
  4.  
  5.     The basic trick used for binary valued variables is the following:
  6.  
  7.     If a[w] and b[w] contain a full word of binary variables, then:
  8.  
  9.      1) to get the full word of their intersection, we use
  10.  
  11.         x = a[w] & b[w];
  12.  
  13.  
  14.      2) to see if the intersection is null in any variables, we examine
  15.  
  16.         x = ~(x | x >> 1) & DISJOINT;
  17.  
  18.     this will have a single 1 in each binary variable for which
  19.     the intersection is null.  In particular, if this is zero,
  20.     then there are no disjoint variables; or, if this is nonzero,
  21.     then there is at least one disjoint variable.  A "count_ones"
  22.     over x will tell in how many variables they have an null
  23.     intersection.
  24.  
  25.  
  26.      3) to get a mask which selects the disjoint variables, we use
  27.  
  28.         (x | x << 1)
  29.  
  30.     this provides a selector which can be used to see where
  31.     they have an null intersection
  32.  
  33.  
  34.     cdist       return distance between two cubes
  35.     cdist0      return true if two cubes are distance 0 apart
  36.     cdist01     return distance, or 2 if distance exceeds 1
  37.     consensus   compute consensus of two cubes distance 1 apart
  38.     force_lower expand hack (for now), related to consensus
  39. */
  40.  
  41. #include "espresso.h"
  42.  
  43. /* see if the cube has a full row of 1's (with respect to cof) */
  44. bool full_row(p, cof)
  45. IN register pcube p, cof;
  46. {
  47.     register int i = LOOP(p);
  48.     do if ((p[i] | cof[i]) != cube.fullset[i]) return FALSE; while (--i > 0);
  49.     return TRUE;
  50. }
  51.  
  52. /*
  53.     cdist0 -- return TRUE if a and b are distance 0 apart
  54. */
  55.  
  56. bool cdist0(a, b)
  57. register pcube a, b;
  58. {
  59.  {  /* Check binary variables */
  60.     register int w, last; register unsigned int x;
  61.     if ((last = cube.inword) != -1) {
  62.  
  63.     /* Check the partial word of binary variables */
  64.     x = a[last] & b[last];
  65.     if (~(x | x >> 1) & cube.inmask)
  66.         return FALSE;               /* disjoint in some variable */
  67.  
  68.     /* Check the full words of binary variables */
  69.     for(w = 1; w < last; w++) {
  70.         x = a[w] & b[w];
  71.         if (~(x | x >> 1) & DISJOINT)
  72.         return FALSE;           /* disjoint in some variable */
  73.     }
  74.     }
  75.  }
  76.  
  77.  {  /* Check the multiple-valued variables */
  78.     register int w, var, last; register pcube mask;
  79.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  80.     mask = cube.var_mask[var]; last = cube.last_word[var];
  81.     for(w = cube.first_word[var]; w <= last; w++)
  82.         if (a[w] & b[w] & mask[w])
  83.         goto nextvar;
  84.     return FALSE;           /* disjoint in this variable */
  85.     nextvar: ;
  86.     }
  87.  }
  88.     return TRUE;
  89. }
  90.  
  91. /*
  92.     cdist01 -- return the "distance" between two cubes (defined as the
  93.     number of null variables in their intersection).  If the distance
  94.     exceeds 1, the value 2 is returned.
  95. */
  96.  
  97. int cdist01(a, b)
  98. register pset a, b;
  99. {
  100.     int dist = 0;
  101.  
  102.  {  /* Check binary variables */
  103.     register int w, last; register unsigned int x;
  104.     if ((last = cube.inword) != -1) {
  105.  
  106.     /* Check the partial word of binary variables */
  107.     x = a[last] & b[last];
  108.     if (x = ~ (x | x >> 1) & cube.inmask)
  109.         if ((dist = count_ones(x)) > 1)
  110.         return 2;
  111.  
  112.     /* Check the full words of binary variables */
  113.     for(w = 1; w < last; w++) {
  114.         x = a[w] & b[w];
  115.         if (x = ~ (x | x >> 1) & DISJOINT)
  116.         if (dist == 1 || (dist += count_ones(x)) > 1)
  117.             return 2;
  118.     }
  119.     }
  120.  }
  121.  
  122.  {  /* Check the multiple-valued variables */
  123.     register int w, var, last; register pcube mask;
  124.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  125.     mask = cube.var_mask[var]; last = cube.last_word[var];
  126.     for(w = cube.first_word[var]; w <= last; w++)
  127.         if (a[w] & b[w] & mask[w])
  128.         goto nextvar;
  129.     if (++dist > 1)
  130.         return 2;
  131.     nextvar: ;
  132.     }
  133.  }
  134.     return dist;
  135. }
  136.  
  137. /*
  138.     cdist -- return the "distance" between two cubes (defined as the
  139.     number of null variables in their intersection).
  140. */
  141.  
  142. int cdist(a, b)
  143. register pset a, b;
  144. {
  145.     int dist = 0;
  146.  
  147.  {  /* Check binary variables */
  148.     register int w, last; register unsigned int x;
  149.     if ((last = cube.inword) != -1) {
  150.  
  151.     /* Check the partial word of binary variables */
  152.     x = a[last] & b[last];
  153.     if (x = ~ (x | x >> 1) & cube.inmask)
  154.         dist = count_ones(x);
  155.  
  156.     /* Check the full words of binary variables */
  157.     for(w = 1; w < last; w++) {
  158.         x = a[w] & b[w];
  159.         if (x = ~ (x | x >> 1) & DISJOINT)
  160.         dist += count_ones(x);
  161.     }
  162.     }
  163.  }
  164.  
  165.  {  /* Check the multiple-valued variables */
  166.     register int w, var, last; register pcube mask;
  167.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  168.     mask = cube.var_mask[var]; last = cube.last_word[var];
  169.     for(w = cube.first_word[var]; w <= last; w++)
  170.         if (a[w] & b[w] & mask[w])
  171.         goto nextvar;
  172.     dist++;
  173.     nextvar: ;
  174.     }
  175.  }
  176.     return dist;
  177. }
  178.  
  179. /*
  180.     force_lower -- Determine which variables of a do not intersect b.
  181. */
  182.  
  183. pset force_lower(xlower, a, b)
  184. INOUT pset xlower;
  185. IN register pset a, b;
  186. {
  187.  
  188.  {  /* Check binary variables (if any) */
  189.     register int w, last; register unsigned int x;
  190.     if ((last = cube.inword) != -1) {
  191.  
  192.     /* Check the partial word of binary variables */
  193.     x = a[last] & b[last];
  194.     if (x = ~(x | x >> 1) & cube.inmask)
  195.         xlower[last] |= (x | (x << 1)) & a[last];
  196.  
  197.     /* Check the full words of binary variables */
  198.     for(w = 1; w < last; w++) {
  199.         x = a[w] & b[w];
  200.         if (x = ~(x | x >> 1) & DISJOINT)
  201.         xlower[w] |= (x | (x << 1)) & a[w];
  202.     }
  203.     }
  204.  }
  205.  
  206.  {  /* Check the multiple-valued variables */
  207.     register int w, var, last; register pcube mask;
  208.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  209.     mask = cube.var_mask[var]; last = cube.last_word[var];
  210.     for(w = cube.first_word[var]; w <= last; w++)
  211.         if (a[w] & b[w] & mask[w])
  212.         goto nextvar;
  213.     for(w = cube.first_word[var]; w <= last; w++)
  214.         xlower[w] |= a[w] & mask[w];
  215.     nextvar: ;
  216.     }
  217.  }
  218.     return xlower;
  219. }
  220.  
  221. /*
  222.     consensus -- multiple-valued consensus
  223.  
  224.     Although this looks very messy, the idea is to compute for r the
  225.     "and" of the cubes a and b for each variable, unless the "and" is
  226.     null in a variable, in which case the "or" of a and b is computed
  227.     for this variable.
  228.  
  229.     Because we don't check how many variables are null in the
  230.     intersection of a and b, the returned value for r really only
  231.     represents the consensus when a and b are distance 1 apart.
  232. */
  233.  
  234. void consensus(r, a, b)
  235. INOUT pcube r;
  236. IN register pcube a, b;
  237. {
  238.     INLINEset_clear(r, cube.size);
  239.  
  240.  {  /* Check binary variables (if any) */
  241.     register int w, last; register unsigned int x;
  242.     if ((last = cube.inword) != -1) {
  243.  
  244.     /* Check the partial word of binary variables */
  245.     r[last] = x = a[last] & b[last];
  246.     if (x = ~(x | x >> 1) & cube.inmask)
  247.         r[last] |= (x | (x << 1)) & (a[last] | b[last]);
  248.  
  249.     /* Check the full words of binary variables */
  250.     for(w = 1; w < last; w++) {
  251.         r[w] = x = a[w] & b[w];
  252.         if (x = ~(x | x >> 1) & DISJOINT)
  253.         r[w] |= (x | (x << 1)) & (a[w] | b[w]);
  254.     }
  255.     }
  256.  }
  257.  
  258.  
  259.  {  /* Check the multiple-valued variables */
  260.     bool empty; int var; unsigned int x;
  261.     register int w, last; register pcube mask;
  262.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  263.     mask = cube.var_mask[var];
  264.     last = cube.last_word[var];
  265.     empty = TRUE;
  266.     for(w = cube.first_word[var]; w <= last; w++)
  267.         if (x = a[w] & b[w] & mask[w])
  268.         empty = FALSE, r[w] |= x;
  269.     if (empty)
  270.         for(w = cube.first_word[var]; w <= last; w++)
  271.         r[w] |= mask[w] & (a[w] | b[w]);
  272.     }
  273.  }
  274. }
  275.  
  276. /*
  277.     cactive -- return the index of the single active variable in
  278.     the cube, or return -1 if there are none or more than 2.
  279. */
  280.  
  281. int cactive(a)
  282. register pcube a;
  283. {
  284.     int active = -1, dist = 0, bit_index();
  285.  
  286.  {  /* Check binary variables */
  287.     register int w, last;
  288.     register unsigned int x;
  289.     if ((last = cube.inword) != -1) {
  290.  
  291.     /* Check the partial word of binary variables */
  292.     x = a[last];
  293.     if (x = ~ (x & x >> 1) & cube.inmask) {
  294.         if ((dist = count_ones(x)) > 1)
  295.         return -1;        /* more than 2 active variables */
  296.         active = (last-1)*(BPI/2) + bit_index(x) / 2;
  297.     }
  298.  
  299.     /* Check the full words of binary variables */
  300.     for(w = 1; w < last; w++) {
  301.         x = a[w];
  302.         if (x = ~ (x & x >> 1) & DISJOINT) {
  303.         if ((dist += count_ones(x)) > 1)
  304.             return -1;        /* more than 2 active variables */
  305.         active = (w-1)*(BPI/2) + bit_index(x) / 2;
  306.         }
  307.     }
  308.     }
  309.  }
  310.  
  311.  {  /* Check the multiple-valued variables */
  312.     register int w, var, last;
  313.     register pcube mask;
  314.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  315.     mask = cube.var_mask[var];
  316.     last = cube.last_word[var];
  317.     for(w = cube.first_word[var]; w <= last; w++)
  318.         if (mask[w] & ~ a[w]) {
  319.         if (++dist > 1)
  320.             return -1;
  321.         active = var;
  322.         break;
  323.         }
  324.     }
  325.  }
  326.  return active;
  327. }
  328.  
  329. /*
  330.     ccommon -- return TRUE if a and b are share "active" variables
  331.     active variables include variables that are empty;
  332. */
  333.  
  334. bool ccommon(a, b, cof)
  335. register pcube a, b, cof;
  336. {
  337.  {  /* Check binary variables */
  338.     int last;
  339.     register int w;
  340.     register unsigned int x, y;
  341.     if ((last = cube.inword) != -1) {
  342.  
  343.     /* Check the partial word of binary variables */
  344.     x = a[last] | cof[last];
  345.     y = b[last] | cof[last];
  346.     if (~(x & x>>1) & ~(y & y>>1) & cube.inmask)
  347.         return TRUE;
  348.  
  349.     /* Check the full words of binary variables */
  350.     for(w = 1; w < last; w++) {
  351.         x = a[w] | cof[w];
  352.         y = b[w] | cof[w];
  353.         if (~(x & x>>1) & ~(y & y>>1) & DISJOINT)
  354.         return TRUE;
  355.     }
  356.     }
  357.  }
  358.  
  359.  {  /* Check the multiple-valued variables */
  360.     int var;
  361.     register int w, last;
  362.     register pcube mask;
  363.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  364.     mask = cube.var_mask[var]; last = cube.last_word[var];
  365.     /* Check for some part missing from a */
  366.     for(w = cube.first_word[var]; w <= last; w++)
  367.         if (mask[w] & ~a[w] & ~cof[w]) {
  368.  
  369.         /* If so, check for some part missing from b */
  370.         for(w = cube.first_word[var]; w <= last; w++)
  371.             if (mask[w] & ~b[w] & ~cof[w])
  372.             return TRUE;            /* both active */
  373.         break;
  374.         }
  375.     }
  376.  }
  377.     return FALSE;
  378. }
  379.  
  380. /*
  381.     These routines compare two sets (cubes) for the qsort() routine and
  382.     return:
  383.  
  384.     -1 if set a is to precede set b
  385.      0 if set a and set b are equal
  386.      1 if set a is to follow set b
  387.  
  388.     Usually the SIZE field of the set is assumed to contain the size
  389.     of the set (which will save recomputing the set size during the
  390.     sort).  For distance-1 merging, the global variable cube.temp[0] is
  391.     a mask which mask's-out the merging variable.
  392. */
  393.  
  394. /* descend -- comparison for descending sort on set size */
  395. int descend(a, b)
  396. pset *a, *b;
  397. {
  398.     register pset a1 = *a, b1 = *b;
  399.     if (SIZE(a1) > SIZE(b1)) return -1;
  400.     else if (SIZE(a1) < SIZE(b1)) return 1;
  401.     else {
  402.     register int i = LOOP(a1);
  403.     do
  404.         if (a1[i] > b1[i]) return -1; else if (a1[i] < b1[i]) return 1;
  405.     while (--i > 0);
  406.     }
  407.     return 0;
  408. }
  409.  
  410. /* ascend -- comparison for ascending sort on set size */
  411. int ascend(a, b)
  412. pset *a, *b;
  413. {
  414.     register pset a1 = *a, b1 = *b;
  415.     if (SIZE(a1) > SIZE(b1)) return 1;
  416.     else if (SIZE(a1) < SIZE(b1)) return -1;
  417.     else {
  418.     register int i = LOOP(a1);
  419.     do
  420.         if (a1[i] > b1[i]) return 1; else if (a1[i] < b1[i]) return -1;
  421.     while (--i > 0);
  422.     }
  423.     return 0;
  424. }
  425.  
  426.  
  427. /* lex_order -- comparison for "lexical" ordering of cubes */
  428. int lex_order(a, b)
  429. pset *a, *b;
  430. {
  431.     register pset a1 = *a, b1 = *b;
  432.     register int i = LOOP(a1);
  433.     do
  434.     if (a1[i] > b1[i]) return -1; else if (a1[i] < b1[i]) return 1;
  435.     while (--i > 0);
  436.     return 0;
  437. }
  438.  
  439.  
  440. /* d1_order -- comparison for distance-1 merge routine */
  441. int d1_order(a, b)
  442. pset *a, *b;
  443. {
  444.     register pset a1 = *a, b1 = *b, c1 = cube.temp[0];
  445.     register int i = LOOP(a1);
  446.     register unsigned int x1, x2;
  447.     do
  448.     if ((x1 = a1[i] | c1[i]) > (x2 = b1[i] | c1[i])) return -1;
  449.     else if (x1 < x2) return 1;
  450.     while (--i > 0);
  451.     return 0;
  452. }
  453.  
  454.  
  455. /* desc1 -- comparison (without indirection) for descending sort */
  456. /* also has effect of handling NULL pointers,and a NULL pointer has smallest
  457. order */
  458. int desc1(a, b)
  459. register pset a, b;
  460. {
  461.     if (a == (pset) NULL)
  462.     return (b == (pset) NULL) ? 0 : 1;
  463.     else if (b == (pset) NULL)
  464.     return -1;
  465.     if (SIZE(a) > SIZE(b)) return -1;
  466.     else if (SIZE(a) < SIZE(b)) return 1;
  467.     else {
  468.     register int i = LOOP(a);
  469.     do
  470.         if (a[i] > b[i]) return -1; else if (a[i] < b[i]) return 1;
  471.     while (--i > 0);
  472.     }
  473.     return 0;
  474. }
  475.